package com.example.demo.leetcode;

/**
 * https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/03/07 15:16
 */
public class _142_环形链表Ⅱ {

    public static void main(String[] args) {
        ListNode node4 = new ListNode(-4);
        ListNode node3 = new ListNode(0, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node = new ListNode(3, node2);
        node4.next = node2;

        ListNode node1 = detectCycle(node);
        System.out.println(node1.val);
    }

    /**
     * 方法一：快慢指针
     * <p>
     * 时间复杂度：O(N) <br>
     * 空间复杂度：O(1) <br>
     *
     * @param head 链表头节点
     * @return {@link ListNode}
     * @author WangYX
     * @date 2024/03/07 15:45
     */
    public static ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}
